Section: New Results

Algèbre max-plus, déformations et asymptotiques /Max-plus algebra, deformations and asymptotic analysis

Introduction

Comme indiqué dans le § 3.7 , l'algèbre max-plus est la limite d'une déformation de l'algèbre classique, ou plutôt du semi-corps des réels positifs. Elle peut aussi fournir des estimations de ces déformations, puisque

L'utilisation de ces propriétés a déjà conduit dans le passé aux travaux sur les perturbations de valeurs propres  [75] , [74] , [73] , ou sur les grandes déviations [1] , [77] . Dans les travaux qui suivent, nous exploitons ces propriétés dans des contextes reliés ou similaires à ceux de nos travaux précédents.

English version

As detailled in § 3.7 , max-plus algebra is the limit of a deformation of classical algebra, or more precisely of the semi-field of usual real positive numbers. It can also give estimations for these deformations using for instance (11 ). By using these properties, we already obtained some works on singular perturbations of matrix eigenvalues  [75] , [74] , [73] , or on large deviations [1] , [77] . In the works described below, we are exploiting again these properties in contexts that are related or similar to those of our earlier works.

Aspects tropicaux des algorithmes de scaling matriciel/Tropical aspects of matrix scaling problems

Participants : Marianne Akian, Stéphane Gaubert, Laura Grigori, Meisam Sharify Najafabadi.

Le travail de thèse de M. Sharify [13] a porté sur les méthodes de mise à l'échelle utilisées en algorithmique numérique matricielle pour améliorer la précision des calculs.

Une première partie du travail, appliquant les techniques de  [73] , [74] , porte sur les problèmes de valeurs propres. On montre notamment que l'ordre de grandeur des valeurs propres d'un faisceau matriciel est donné (sous des conditions de non-dégénerescence) par les valeurs tropicales, qui peuvent être calculées de manière robuste, et fournissent ainsi une mise à l'échelle pour calculer les valeurs propres classiques.

Une seconde partie du travail (collaboration avec L. Grigori) porte sur le calcul de mises-à-l'échelle issues de la résolution d'un problème d'affectation optimale. On a développé un algorithme dont l'idée est de voir le problème d'affectation comme une limite d'un problème de maximisation d'entropie. Ceci conduit à un préprocessing parallèle, qui permet d'éliminer a priori des coefficients qui ne participent pas aux affectations optimales, de sorte que le problème réduit devient résoluble sur une machine séquentielle. L'algorithme ainsi obtenu est étudié dans le preprint [69] , qui comprend également des résultats expérimentaux.

English version

The PhD work of M. Sharify [13] deals with the development of scaling methods in matrix analysis to improve the accuracy of numerical computions.

A first part of the work, applying the techniques of  [73] , [74] , deals with eigenvalue problems. We show in particular that the order of magnitude of the eigenvalues of a matrix pencil can be determined (under nondegeracy conditions) by computing tropical eigenvalues. The latter can always be computed accurately and provide a scaling which can be combined with standard numerical methods for matrix pencils.

A second part of the work (collaboration with L. Grigori) deals with the parallel computation of scalings based on the optimal assignment problem. The latter is thought of as a limit of an entropy maximization problem. This leads to a parallel preprocessing, allowing one to eliminate a priori entries which do not belong to optimal assignment, so that the reduced problem becomes solvable on a sequential machine. This algorithm is studied in the preprint [69] , which also comprises experimental results.

Mesures et applications maxitives

Participants : Marianne Akian, Paul Poncet.

Les mesures et intégrales maxitives qui ont été introduites et ré-introduites sous divers noms dans la littérature (intégrale de Shilkret, sup-mesures, mesures de possibilité, mesures idempotentes de Maslov, etc.), sont définies de manière analogue aux mesures et intégrales usuelles, en remplaçant les lois additive et multiplicative par celles d'un semi-anneau idempotent, comme par exemple le semi-anneau max-plus. Elles peuvent aussi être obtenues comme limites de mesures positives après déformation logarithmique, par le principe des grandes déviations. Entre autres motivations à l'étude de ces mesures, citons les processus max-stables et leur représentation intégrale, les processus extrêmes, ou les grandes déviations à la loi des grands nombres.

Le travail de thèse de Paul Poncet [12] est parti de ces motivations. Il traite essentiellement de ce que l'on appelle l'analyse idempotente, c'est-à dire l'étude des espaces fonctionnels ou linéaires de dimension infinie sur l'algèbre tropicale, ou tout autre semi-anneau idempotent. Paul Poncet a développé pour cela un point de vue treillis continus comme dans [1] , ou plus généralement domaines, et ses travaux pourraient donc aussi avoir des applications en informatique.

La première partie de la thèse traite des mesures maxitives. Paul Poncet a donné une revue des résultats existants concernant l'existence d'une densité cardinale ou d'une densité d'une mesure par rapport à une autre (théorème de Radon-Nikodym), et la régularité d'une mesure maxitive, tout en les comparant et les complétant. En particulier il prouve une réciproque au théorème de Radon-Nikodym pour les mesures maxitives, c'est-à-dire qu'il donne une caractérisation des mesures maxitives ayant la propriété de Radon-Nikodym, il caractérise les mesures maxitives régulières à valeurs dans un domaine, donne un théorème de décomposition des mesures maxitives aussi publié dans [34] , et donne un théorème de représentation de Riesz pour les formes linéaires max-plus continues.

Une deuxième partie concerne les convexes dans les semi-treillis ou l'algèbre max-plus. Paul Poncet s'est intéressé à l'existence d'un théorème de type Krein-Milman, à sa réciproque de Milman, et à celle d'un théorème de type représentation de Choquet dans ces structures. Dans le cas des semi-treillis, certains de ces résultats se déduisent rapidement des travaux sur les semi-treillis compacts, mais d'autres sont entièrement nouveaux. Le théorème de Krein-Milman pour les convexes tropicaux, qui n'avait été établi dans la littérature qu'en dimension finie  [137] , [96] , [125] , est prouvé en dimension infinie au moyen de celui sur les semi-treillis. Le théorème de représentation de Choquet utilise les notions de mesures maxitives introduites dans la première partie. De tels résultats permettent de retrouver partiellement les résultats sur la frontière de Martin max-plus décrits dans la section  6.1.1 .

Enfin dans une troisième et dernière partie, Paul Poncet étudie les semi-groupes inverses dans une tentative d'unification de l'algèbre usuelle et de l'algèbre tropicale.

English version

Maxitive measures and integrals, which have been introduced and re-introduced under different names in the literature (Shilkret integral, sup-measures, possibility measures, Maslov idempotent measures, etc.), are defined analogously to usual measures and integrals, by replacing the additive and multiplicative laws by the laws of an idempotent semiring, such as the max-plus semiring. They can also be obtained as limits of positive measures after logarithmic deformation, by the large deviation principle. Among motivations for the study of this notion, let us mention max-stable processes and their integral representations, extremal processes, or large deviations to the law of large numbers.

The PhD thesis work of Paul Poncet [12] started from these motivations. It concerns essentially what is called idempotent analysis, that is the study of infinite dimensional functional or linear spaces over tropical algebra, or any other idempotent semiring. For this aim, Paul Poncet developped the point of view of continuous lattices, as in [1] , or more generally of domains, and his works may have applications in computer science.

The first part of his thesis concerns maxitive measures. Paul Poncet gave a survey of existing results concerning the existence of a cardinal density of a measure, that of a density of a measure with respect to another (Radon-Nikodym theorem), and the regularity of a maxitive measure, while comparing and extending them. In particular he proves a converse to the Radon-Nikodym theorem for maxitive measures, which lead to a characterisation of maxitive measures that have the Radon-Nikodym property, he characterizes domain valued maxitive measures that are regular, gives a decomposition theorem of maxitive measures also published in [34] , and gives a Riesz representation theorem for continuous max-plus linear forms.

A second part concerns convex sets in lattices or max-plus algebra. Paul Poncet is showing a Krein-Milman type theorem, its Milman converse, or a Choquet representation type theorem in these structures. In the case of semilattices, some of these results can be deduced easily from works on compact semilattices, but some others are new. The Krein-Milman on tropical convex sets, which in the litterature was established in finite dimension only  [137] , [96] , [125] , is deduced in infinite dimension from the analogous result concerning semilattices. The Choquet representation theorem uses the notions of maxitive measures introduced in the first part. Such results lead in particular to new proofs of some of the results on Martin boundaries described in Section  6.1.1 .

In the third and last part, Paul Poncet is studying inverse semigroups in an attempt to unify usual and tropical algebras.